package demo4;

import lombok.AllArgsConstructor;
import lombok.Getter;
import lombok.NoArgsConstructor;
import lombok.Setter;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.concurrent.atomic.AtomicInteger;

public class TreeAndGraph {
    public InorderSucc makeUpInorderSucc() {
        return new InorderSucc();
    }

    public BSTCheckB makeUPBSTCheckB() {
        return new BSTCheckB();
    }

    public BSTCheck makeUPBSTCheck() {
        return new BSTCheck();
    }

    public BalanceImproved makeUpBalanceImproved() {
        return new BalanceImproved();
    }

    public BalanceBrute makeUpBalanceBrute() {
        return new BalanceBrute();
    }

    public Graph makeUpGraph() {
        Graph graph = new Graph();
        return graph;
    }

    public TreeSequence makeUpTreeSequence() {
        return new TreeSequence();
    }

    public CommonAncestor1 makeUpCommonAncestor1() {
        return new CommonAncestor1();
    }

    public CommonAncestor2 makeUpCommonAncestor2() {
        return new CommonAncestor2();
    }

    public CommonAncestor3 makeUpCommonAncestor3() {
        return new CommonAncestor3();
    }

    public CommonAncestor4 makeUpCommonAncestor4() {
        return new CommonAncestor4();
    }

    public CommonAncestor5 makeUpCommonAncestor5() {
        return new CommonAncestor5();
    }

    public NodeForTree makeUpNodeForTree(int data) {
        return new NodeForTree(data);
    }

    public CheckBST makeUpCheckBST() {
        return new CheckBST();
    }

    public SumTrace makeUpSumTrace() {
        return new SumTrace();
    }
    public SumTraceWithHashMap makeUpSumTraceWithHashMap(){
        return new SumTraceWithHashMap();
    }

    public NodeForTree makeUpNodeForTreeWithDefaultVal() {
        return new NodeForTree().makeUpMinimumBinarySearchTreeWithoutRecusion();
    }

    public NodeForTree makeUpNodeForTreeWithSpecialMethod(int[] arrays) {
        NodeForTree nodeForTree = new NodeForTree();
        return nodeForTree.makeUpNodeForTreeWithSpecialMethod(arrays);

    }

    public NodeForTree makeUpNodeForTreeWithRecusionSame(int[] arrays) {

        NodeForTree nodeForTree = new NodeForTree();
        return nodeForTree.makeUpMinimumBinarySearchTreeWithRecusion(arrays, 0, arrays.length - 1);
    }


    @Setter
    @Getter
    @NoArgsConstructor
    public class Node {
        private Node next;
        private int data;
        private char character;
        private boolean visited;
        private Node[] adjacent;
        private int heigh;

        public Node(char character) {
            this.character = character;
        }

        public Node(int data) {
            this.data = data;
        }

    }

    @Getter
    @Setter
    public class SumTraceWithHashMap {

        public void changeRoot(NodeForTree nodeForTree, HashMap<NodeForTree, ArrayList<ArrayList<Integer>>> map) {
            if (nodeForTree == null) {
               return;
            }
            changeRoot(nodeForTree.left, map);
            changeRoot(nodeForTree.right, map);


            map.computeIfAbsent(nodeForTree, (v) -> {
                return new ArrayList<ArrayList<Integer>>();
            });
            if(nodeForTree!=null){
                 // 3=>0,3  5=>0,5
                //  4=>1,0,3 6=>1,0,5 1=>1,0 3=>1,2 1=>1
                //  root=1;
                map.compute(nodeForTree,(k,v)->{

                    if(nodeForTree.left!=null){
                        map.compute(nodeForTree.left,(k1,v1)->{
                            for (ArrayList<Integer> list : v1) {

                                ArrayList<Integer> integers = new ArrayList<>();
                                // 3,1,0 | 3,1,2 | 3,1 | 3

                                integers.add(nodeForTree.data);
                                for (Integer integer : list) {
                                    integers.add(integer);
                                }
                                v.add(integers);
                                // 1,
                                ArrayList<Integer> integers1 = new ArrayList<>();
                                integers1.add(nodeForTree.data);
                                v.add(integers1);
                            }
                            return v1;
                        });

                    }else{
                        v.add(new ArrayList<Integer>(){{
                            add(nodeForTree.data); // 3
                        }});
                    }

                     return v;
                 });

                map.compute(nodeForTree,(k,v)->{

                    if(nodeForTree.right!=null){
                        map.compute(nodeForTree.right,(k1,v1)->{
                            for (ArrayList<Integer> list : v1) {
                                    ArrayList<Integer> integers = new ArrayList<>();
                                    // 1,0,3 | 1,0,5
                                    integers.add(nodeForTree.data);
                                    for (Integer integer : list) {
                                        integers.add(integer);
                                    }
                                    v.add(integers);

                            }
                            return v1;
                        });

                    }

                    return v;
                });

            }




        }

        public HashMap<Integer, ArrayList<ArrayList<Integer>>> sumMap(HashMap<TreeAndGraph.NodeForTree, ArrayList<ArrayList<Integer>>> map) {
            HashMap<Integer, ArrayList<ArrayList<Integer>>> sumMap = new HashMap<>();
            map.values().stream().forEach((kv)->{
                kv.stream().forEach(kv1->{
                    kv1.stream().reduce(Integer::sum).ifPresent(sum->{
                            sumMap.computeIfAbsent(sum,(v)->{
                                return new ArrayList<>();
                            });
                            sumMap.compute(sum,(k, v)->{
                               v.add(kv1);
                               return v;
                            });
                    });
                });
            });
            return sumMap;
        }
    }

    @Getter
    @Setter
    public class SumTrace {
        // O(logN)
        public boolean getTraceWithSum(int val, NodeForTree node, LinkedList<Integer> list) {
            if (node == null) {
                return false;
            }
            if (val - node.data == 0) {
                list.addFirst(node.data);
                return true;
            }
            boolean flag1 = getTraceWithSum(val - node.data, node.left, list);
            boolean flag2 = getTraceWithSum(val - node.data, node.right, list);
            if (flag1 || flag2) {
                list.addFirst(node.data);
            }

            return flag1 || flag2;

        }

        // O(N)
        public void changeRoot(int val, NodeForTree nodeForTree, ArrayList<LinkedList<Integer>> arrayList) {
            if (nodeForTree == null) {
                return;
            }
            changeRoot(val, nodeForTree.left, arrayList);
            changeRoot(val, nodeForTree.right, arrayList);

            LinkedList<Integer> linkedList1 = new LinkedList<>();
            boolean traceWithSum = getTraceWithSum(val, nodeForTree, linkedList1);
            if (traceWithSum) {
                arrayList.add(linkedList1);
            }
        }
    }

    /**
     *
     */
    @Setter
    @Getter
    public class CheckBST {

        /**
         * Node node1 , Node node2
         * every
         * double for loop
         * 1+2+3+..n=n(n+1)/2 =100(101)/2 =5050
         * 2+4+..+n  =
         * n/2 + n/4 +..1=n(n+1)/2~ n^2
         */
        public boolean iterate(NodeForTree node1, NodeForTree node2) {
            if (node1 == null) {
                return false;
            }
            boolean flag1 = iterate(node1.left, node2);
            boolean flag2 = iterate(node1.right, node2);
            if (flag1 || flag2) {
                return true;
            }
            return check(node1, node2);
        }

        /**
         *
         */
        private boolean check(NodeForTree node1, NodeForTree node2) {
            ArrayList<Integer> nodeForTrees1 = new ArrayList<>();
            ArrayList<Integer> nodeForTrees2 = new ArrayList<>();

            preOrderTraversal(node1, nodeForTrees1);
            preOrderTraversal(node2, nodeForTrees2);

            return assertArrayEqualsMethodTwo(nodeForTrees1, nodeForTrees2);

        }

        private boolean assertArrayEqualsMethodTwo(ArrayList<Integer> nodeForTrees1, ArrayList<Integer> nodeForTrees2) {
            if (nodeForTrees1.size() != nodeForTrees2.size()) {
                return false;
            }
            nodeForTrees1.removeAll(nodeForTrees2);
            return nodeForTrees1.size() == 0;

        }

        private boolean assertArrayEquals(int[] expected, int[] actual) {
            if (expected.length != actual.length) {
                return false;
            }
            for (int i = 0; i < expected.length; i++) {
                if (expected[i] != actual[i]) {
                    return false;
                }
            }
            return true;
        }

        public void preOrderTraversal(NodeForTree node, ArrayList<Integer> list) {
            //
            if (node != null) {
                list.add(node.data);
                preOrderTraversal(node.left, list);
                preOrderTraversal(node.right, list);
            }

        }

        public void inOrderTraversal(NodeForTree node, ArrayList<Integer> list) {
            if (node != null) {
                inOrderTraversal(node.left, list);
                list.add(node.data);
                inOrderTraversal(node.right, list);
            }

        }

    }

    @Setter
    @Getter
    public class TreeSequence {

        /**
         *
         */
        public ArrayList<LinkedList<Integer>> allSequence(NodeForTree node) {
            ArrayList<LinkedList<Integer>> linkedLists = new ArrayList<>();
            if (node == null) {
                linkedLists.add(new LinkedList<Integer>());
                return linkedLists;
            }
            LinkedList<Integer> prefix = new LinkedList<>();
            prefix.addLast(node.data);

            ArrayList<LinkedList<Integer>> left = allSequence(node.left);

            ArrayList<LinkedList<Integer>> right = allSequence(node.right);

            for (LinkedList<Integer> leftList : left) { // 0

                for (LinkedList<Integer> rightList : right) { // 2
                    ArrayList<LinkedList<Integer>> singleSequence = new ArrayList<>();
                    weaveList(leftList, rightList, singleSequence, prefix);
                    linkedLists.addAll(singleSequence);
                }
            }
            return linkedLists;
        }

        private void weaveList(LinkedList<Integer> leftList, LinkedList<Integer> rightList, ArrayList<LinkedList<Integer>> linkedLists, LinkedList<Integer> prefix) {
            if (leftList.size() == 0 || rightList.size() == 0) {
                LinkedList<Integer> clone = (LinkedList<Integer>) prefix.clone();

                clone.addAll(leftList);
                clone.addAll(rightList);
                linkedLists.add(clone);
                return;
            }
            Integer integer = leftList.removeFirst();
            prefix.addLast(integer);
            weaveList(leftList, rightList, linkedLists, prefix);
            leftList.addFirst(integer);
            prefix.removeLast();


            Integer integer1 = rightList.removeFirst();
            prefix.add(integer1);
            weaveList(leftList, rightList, linkedLists, prefix);
            rightList.addFirst(integer1);
            prefix.removeLast();


        }

    }

    @Setter
    @Getter
    public class CommonAncestor5 {
        @Setter
        @Getter
        @AllArgsConstructor
        @NoArgsConstructor
        public class Result {
            private NodeForTree node;
            private boolean ancestor;
        }

        public Result commonAncestor(NodeForTree root, NodeForTree first, NodeForTree second) {
            if (root == null) {
                return new Result(null, false);
            }
            if (root == first && second == root) {
                return new Result(first, true);
            }
            Result result1 = commonAncestor(root.left, first, second);
            if (result1.isAncestor()) {
                return result1;
            }
            Result result2 = commonAncestor(root.right, first, second);
            if (result2.isAncestor()) {
                return result2;
            }
            if (result1.node != null && result2.node != null) {
                return new Result(root, true);
            } else if (root == first || root == second) {
                if (result1.node != null || result2.node != null) {
                    return new Result(root, true);
                } else {
                    return new Result(root, false);
                }
            } else {
                NodeForTree tmp = result1.node != null ? result1.node : result2.node;
                return new Result(tmp, false);
            }
        }

    }

    @Setter
    @Getter
    public class CommonAncestor4 {
        public NodeForTree commonAncestor(NodeForTree root, NodeForTree first, NodeForTree second) {
            if (root == null || root == first || root == second) { // 3=3
                return root;
            }
            boolean isFirstLeft = covers(root.left, first);
            boolean isSecondLeft = covers(root.left, second);
            if (first != second) {
                return root;
            }
            NodeForTree childSide = isFirstLeft ? root.left : root.right; // childSide=right
            return commonAncestor(childSide, first, second);
        }

        public boolean covers(NodeForTree node, NodeForTree second) {
            if (node == null) {
                return false;
            }
            if (node == second) {
                return true;
            }

            return covers(node.left, second) || covers(node.right, second);
        }

    }

    @Setter
    @Getter
    public class CommonAncestor3 {
        public NodeForTree commonAncestor(NodeForTree root, NodeForTree first, NodeForTree second) {
            if (!covers(root, first) || !covers(root, second)) {
                return null;
            } else if (covers(first, second)) {
                return first;
            } else if (covers(second, first)) {
                return second;
            }
// ie: 2 ,4
            NodeForTree parent = first.parent;
            NodeForTree sibling = getSibling(first);

            while (!covers(sibling, second)) {
                sibling = getSibling(parent);
                if (parent != null) {
                    parent = parent.parent;
                } else {
                    return null;
                }

            }
            return parent;

        }

        public NodeForTree getSibling(NodeForTree node) {
            if (node != null && node.parent != null) {
                return node == node.parent.left ? node.parent.right : node.parent.left;
            }
            return null;
        }

        public boolean covers(NodeForTree node, NodeForTree second) {
            if (node == null) {
                return false;
            }
            if (node == second) {
                return true;
            }

            return covers(node.left, second) || covers(node.right, second);
        }

    }

    @Getter
    @Setter
    public class CommonAncestor2 {
        public NodeForTree commonAncestor(NodeForTree first, NodeForTree second) {
            int depth1 = depth(first);
            int depth2 = depth(second);

            NodeForTree shallow = depth1 > depth2 ? second : first; // shallow;
            NodeForTree deeper = depth1 > depth2 ? first : second; // deepers
            deeper = goUpByDiff(deeper, Math.abs(depth1 - depth2));// move shallow to depth of deeper
            while (shallow != deeper && shallow != null && deeper != null) {
                shallow = shallow.parent;
                deeper = deeper.parent;
            }
            return shallow == null || deeper == null ? null : shallow;

        }

        public NodeForTree goUpByDiff(NodeForTree shallow, int diff) {

            while (shallow != null && diff > 0) {
                shallow = shallow.parent;
                diff--;
            }
            return shallow;
        }

        public int depth(NodeForTree node) {
            int depth = 0;
            while (node != null) {
                node = node.parent;
                depth++;
            }
            return depth;
        }

    }

    @Getter
    @Setter
    public class CommonAncestor1 {
        /**
         * know the parent ,
         * double for loop
         */
        public NodeForTree findCommonAncestor(NodeForTree first, NodeForTree second) {
            if (first == second) {
                return first;
            }
            NodeForTree ancestor = first;
            while (ancestor != null && ancestor != second) {
                if (!isOnePath(ancestor, second)) {
                    ancestor = ancestor.parent;
                } else {
                    return ancestor;
                }
            }
            return (ancestor == second) ? ancestor : null;

        }

        public boolean isOnePath(NodeForTree ancestor, NodeForTree node) {
            while (node != null && ancestor != node) {
                node = node.parent;
            }
            return !(ancestor != node);
        }


    }

    @Getter
    @Setter
    public class CommonAncestor {

        public NodeForTree findCommonAncestor(NodeForTree node, NodeForTree first, NodeForTree second, boolean isLeft) {
            // find first location ,left or right
            if (node == null) {
                return null;
            }
            if (node == first) {
                node.setIsleft(isLeft);
            }
            if (node == second) {
                node.setIsleft(isLeft);
            }

            findCommonAncestor(node.left, first, second, true);
            findCommonAncestor(node.right, first, second, false);

            return node;
        }

    }

    @Getter
    @Setter
    public class InorderSucc {
        public NodeForTree inorderSucc(NodeForTree node) {
            if (node == null) {
                return null;
            }

            if (node.parent == null || node.right != null) {
                return getMostLeftFromRightNode(node.right);
            }

            NodeForTree x = node;
            NodeForTree p = node.parent;

            while (p != null && p.left != x) {
                x = p;
                p = p.parent;
            }
            return p;
        }

        private NodeForTree getMostLeftFromRightNode(NodeForTree node) {
            if (node == null) {
                return null;
            }
            while (node.left != null) {
                node = node.left;
            }
            return node;
        }

    }

    @Getter
    @Setter
    public class BSTCheckB {
        public boolean isBST(NodeForTree node, Integer min, Integer max) {
            if (node == null) {
                return true;
            }
            if ((min != null && min >= node.data) || (max != null && max < node.data)) {
                return false;
            }
            // false || true
            if (!isBST(node.left, min, node.data) || !isBST(node.right, node.data, max)) {
                return false;
            }
            ;
            return true;
        }

    }

    @Getter
    @Setter
    public class BSTCheck {
        private Integer lastPrint = null;

        public boolean isBST(NodeForTree node, boolean isLeft) {
            if (node == null) {
                return true;
            }
            if (!isBST(node.left, true)) {
                return false;
            }
            if (lastPrint != null) {
                if (isLeft) {
                    // allow left child <= parent ,
                    if (node.data < lastPrint) {
                        return false;
                    }
                } else {
                    if (node.data <= lastPrint) {
                        return false;
                    }
                }
            }
            lastPrint = node.data;
            if (!isBST(node.right, false)) {
                return false;
            }

            return true;
        }
    }

    @Getter
    @Setter
    public class BalanceImproved {
        public int checkHeight(NodeForTree root) {
            if (root == null) {
                return -1;
            }
            int leftdata = checkHeight(root.left);
            if (leftdata == Integer.MIN_VALUE) {
                return Integer.MIN_VALUE;
            }
            int rightdata = checkHeight(root.right);
            if (rightdata == Integer.MIN_VALUE) {
                return Integer.MIN_VALUE;
            }
            int diff = leftdata - rightdata;
            if (Math.abs(diff) > 1) {
                System.out.println("the diff is " + diff + " is not Balanced , current root node is : " + root.data);
                return Integer.MIN_VALUE;
            } else {
                return Math.max(leftdata, rightdata) + 1;
            }

        }

        public boolean isBalanced(NodeForTree root) {
            return checkHeight(root) != Integer.MIN_VALUE;
        }
    }

    @Getter
    @Setter
    public class BalanceBrute {
        public int getHeight(NodeForTree root) {
            if (root == null) {
                return -1;
            }
            return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
        }

        public boolean isBalanced(NodeForTree root) {
            if (root == null) return true;

            int sub = getHeight(root.left) - getHeight(root.right);
            if (Math.abs(sub) > 1) {
                System.out.println("the diff is " + sub + " is not Balanced , current root node is : " + root.data);
                return false;
            } else {
                return isBalanced(root.left) && isBalanced(root.right);
            }

        }

    }


    @Getter
    @Setter
    public class NodeForTree {
        private NodeForTree left;
        private NodeForTree right;
        private NodeForTree parent;
        private boolean isleft;
        private int data;
        private int[] arrays;

        @Override
        public boolean equals(Object obj) {
            return super.equals(obj);
        }

        @Override
        public int hashCode() {
            return super.hashCode();
        }

        public NodeForTree() {
        }

        public NodeForTree(int data) {
            this.data = data;
        }

        //        private int[] arrays=new int[]{1,2,3,5,6,7,8};
        public NodeForTree makeUpMinimumBinarySearchTreeWithoutRecusion() {
            NodeForTree nodeForTree5 = new NodeForTree(5);
            NodeForTree nodeForTree2 = new NodeForTree(2);
            NodeForTree nodeForTree7 = new NodeForTree(7);
            NodeForTree nodeForTree1 = new NodeForTree(1);
            NodeForTree nodeForTree3 = new NodeForTree(3);
            NodeForTree nodeForTree6 = new NodeForTree(6);
            NodeForTree nodeForTree8 = new NodeForTree(8);

            nodeForTree2.left = nodeForTree1;
            nodeForTree2.right = nodeForTree3;
            nodeForTree5.left = nodeForTree2;
            nodeForTree5.right = nodeForTree7;
            nodeForTree7.left = nodeForTree6;
            nodeForTree7.right = nodeForTree8;

            return nodeForTree5;
        }

        public int getHeigh() {
            int leftHeigh = this.left == null ? 0 : this.left.getHeigh();
            int rightHeigh = this.right == null ? 0 : this.right.getHeigh();

            return Math.max(leftHeigh, rightHeigh) + 1;
        }

        // makeUp the BST
        public void inOrderInsert(int d) {
            if (this.data > d) {
                if (this.left == null) {
                    this.left = new NodeForTree(d);
                } else {
                    this.left.inOrderInsert(d);
                }

            } else {
                if (right == null) {
                    this.right = new NodeForTree(d);
                } else {
                    this.right.inOrderInsert(d);
                }
            }
        }

        // bst search  begin from mediumnode
        public NodeForTree find(int data, NodeForTree node) {
            if (node == null) {
                return null;
            }
            if (data > node.data) {
                return find(data, node.right);
            } else if (data == node.data) {
                return node;
            } else {
                return find(data, node.left);
            }
        }

        public void inOrderTraversal(NodeForTree node) {
            if (node != null) {
                inOrderTraversal(node.left); //
                visit(node); //
                inOrderTraversal(node.right); //
            }
        }

        public void preOrderTraversal(NodeForTree node) {
            if (node != null) {
                visit(node);
                preOrderTraversal(node.left);
                preOrderTraversal(node.right);
            }
        }

        public void postOrderTraversal(NodeForTree node) {
            if (node != null) {
                postOrderTraversal(node.left);
                postOrderTraversal(node.right);
                visit(node);
            }
        }

        private void visit(NodeForTree node) {
            System.out.println("current search node is " + node.data);
        }

        /**
         *
         */
        public NodeForTree makeUpMinimumBinarySearchTreeWithRecusion(int[] arrays, int start, int end) {
            if (end < start) {
                return null;
            }
            int mid = (start + end) / 2; // 1
            NodeForTree node = new NodeForTree(arrays[mid]);
            // node(0)  => node(0).left => 0,-1 (return null)
            node.left = makeUpMinimumBinarySearchTreeWithRecusion(arrays, start, mid - 1);
            if (node.left != null) {
                node.left.parent = node;
            }

            node.right = makeUpMinimumBinarySearchTreeWithRecusion(arrays, mid + 1, end);
            if (node.right != null) {
                node.right.parent = node;
            }

            return node;

        }

        public ArrayList<LinkedList<NodeForTree>> dfs(NodeForTree root) {
            ArrayList<LinkedList<NodeForTree>> lists = new ArrayList<LinkedList<NodeForTree>>();
            dfs(root, lists, 0);
            return lists;

        }

        public void printResult(ArrayList<LinkedList<NodeForTree>> linkedLists) {
            AtomicInteger depth = new AtomicInteger();
            linkedLists.stream().forEach(linkedList -> {
                System.out.println("current depth is " + depth.get());
                while (!linkedList.isEmpty()) {
                    NodeForTree node = linkedList.removeFirst();
                    System.out.println("current depth val is : " + node.getData());

                }
                depth.getAndIncrement();
            });
        }

        public void dfs(NodeForTree root, ArrayList<LinkedList<NodeForTree>> lists, int level) {
            if (root == null) {
                return;
            }
            LinkedList<NodeForTree> list = null;
            if (lists.size() == level) { // 1!=1
                list = new LinkedList<NodeForTree>();
                lists.add(list);
            } else {
                list = lists.get(level);
            }
            list.add(root);

            dfs(root.left, lists, level + 1);
            dfs(root.right, lists, level + 1);

        }

        public ArrayList<LinkedList<NodeForTree>> bfs(NodeForTree root) {
            ArrayList<LinkedList<NodeForTree>> linkedLists = new ArrayList<LinkedList<NodeForTree>>();
            LinkedList<NodeForTree> current = new LinkedList<NodeForTree>() {
                {
                    add(root);
                }
            };
            while (!current.isEmpty()) {
                linkedLists.add(current); // get previous level
                LinkedList<NodeForTree> parents = current;
                current = new LinkedList<NodeForTree>(); // new next level
                for (NodeForTree parent : parents) {
                    if (parent.left != null) {
                        current.add(parent.left);
                    }
                    if (parent.right != null) {
                        current.add(parent.right);
                    }
                }
            }

            return linkedLists;
        }

        /**
         * 0,1,2
         */
        public NodeForTree makeUpNodeForTreeWithSpecialMethod(int[] arrays) {
            NodeForTree root = new NodeForTree(2);
            root.left = new NodeForTree(0);
            root.right = new NodeForTree(-1);
            root.left.left = new NodeForTree(-1);
            root.left.right = new NodeForTree(2);

            return root;
        }


    }

    /**
     *
     */
    @Getter
    @Setter
    public class Graph {

        private Node node0;
        int heigh = 0;

        // make up graph ,form dfs  then delete graph node , add to list,
        public Graph() {

        }

        public void makeUpAssociation() {
            node0 = new Node(0);
            Node node1 = new Node(1);
            Node node2 = new Node(2);
            Node node3 = new Node(3);
            Node node4 = new Node(4);
            Node node5 = new Node(5);

            node0.adjacent = new Node[]{node1, node5};
            node1.adjacent = new Node[]{node3, node4};
            node2.adjacent = new Node[]{node1};
            node3.adjacent = new Node[]{node2};
            node4.adjacent = new Node[0];
            node5.adjacent = new Node[0];
        }

        public void makeUpProjectDependence() {
            node0 = new Node('f');
            Node node1 = new Node('b');
            Node node2 = new Node('a');
            Node node3 = new Node('d');
            Node node4 = new Node('c');
            Node node5 = new Node('e');

            node0.adjacent = new Node[]{node1, node2};
            node1.adjacent = new Node[]{node3};
            node2.adjacent = new Node[]{node3};
            node3.adjacent = new Node[]{node4};
            node4.adjacent = new Node[0];
            node5.adjacent = new Node[0];
        }

        // setting heigh val;
        public int dfsForHeigh(Node node, int heigh) {
            if (node == null) return 0;
            node.visited = true;
            Node[] adjacent = node.adjacent;
            int length = node.adjacent.length;
            for (int i = 0; i < length; i++) {
                if (adjacent[i].visited == false) { // f, (b ,d,c)
                    heigh = dfsForHeigh(adjacent[i], heigh) + 1;
                    System.out.println("current node " + adjacent[i].getCharacter() + " heigh : " + heigh);
                }
            }
            return heigh;
        }


        // depth-first search

        /**
         * @return demo4.TreeAndGraph.Node
         * @author houchunjian
         * @date 2023/2/17 0017 17:23
         */
        public void dfs(Node node) {
            if (node == null) return;
            visit(node);
            node.visited = true;
            Node[] adjacent = node.adjacent;
            int length = node.adjacent.length;
            for (int i = 0; i < length; i++) {
                if (adjacent[i].visited == false) {
                    dfs(adjacent[i]);
                }
            }

        }

        private void visit(Node node) {
            System.out.println("current search node is " + node.character + "-------node.data is:" + node.data + "----node.heigh is : " + node.heigh);
        }
        // breadth-first search

        /**
         * use queue
         */
        public void bfs(Node node) {
            LinkedList<Node> queue = new LinkedList<Node>();
            node.visited = true;
            queue.addLast(node);
            while (!queue.isEmpty()) {
                Node r = queue.removeFirst();
                visit(r);
                Node[] adjacent = r.adjacent; // 0-> 1,5
                int length = r.adjacent.length;
                for (int i = 0; i < length; i++) {
                    if (adjacent[i].visited == false) {
                        adjacent[i].visited = true;
                        queue.addLast(adjacent[i]);
                    }
                }
            }

        }


    }

}
